package com.ryujung.linked_list.leetCode_83;

/*
排序链表的去重问题

思路:迭代
保存头节点,遍历整个链表,设置一个指针
如果当前节点的值和下一个节点的值相同,则让当前节点指向下下个节点,即跳过重复地节点
否则让指针指向下一个元素
*/
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode temp = head;
        while(temp!=null && temp.next!=null){
            //注意这个判断顺序不能乱,否则null调用next方法,造成空指针异常
            if(temp.val==temp.next.val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        return head;
    }

    /**
     * 递归算法:
     * 
     */
    public ListNode deleteDuplicates2(ListNode head) {
        //递归出口
        if(head==null||head.next==null)return head;
        head.next = deleteDuplicates2(head.next);
        return head.val==head.next.val?head.next:head;
    }
}

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}